package org.rowan.adi.tda.tda2d.services;

import java.util.LinkedList;
import org.rowan.adi.Vector;
import org.rowan.adi.components.comp2d.Component2D;
import org.rowan.adi.components.comp2d.LineSegment2D;
import org.rowan.adi.components.comp2d.Point2D;
import org.rowan.adi.components.comp2d.polygon.Polygon;
import org.rowan.adi.components.comp2d.polygon.Rectangle;
import org.rowan.adi.linearalgebra.LinearAlgebra2D;

/**
 * The Optimization2D class is a type of Service, as it implemements the
 * Service2D interface. This service will reposition the low-level 2D components
 * of a DecisionManager2D so they optimially cover the high-level area. This class
 * can produce the best-case or worst-case solution
 *
 * @author Charles Dugenio, Jonathan Palka
 * @version 1.0
 */
public class Optimization2D implements Service2D {

    private Polygon highLevelComponent; // The high level component of a decision aid.
    private LinkedList<Polygon> lowLevelComponents; // The low-level components within a decision aid.
    private boolean contained;  //Do low-level components have to stay inside of high level area.
    private boolean overLap;    //Can low-level components over lap
    private boolean bestCase;   //best or worst case?

    /**
     * Constructs an instance of Optimization2D. By default, it is assumed
     * that low-level components are not allowed to intersect the high-level area
     * and low-level components can intersect.
     * @param highLevelComponent the high level 2D component within a DecisionManager2D.
     * @param lowLevelComponents the low-level 2D components within a DecisionManager2D.
     * @param case <true> if the best-case, or finding the optimizal solution, is desired;
     * <code>false</code> otherwise, which means the worst-case solution will be found.
     */
    public Optimization2D(Polygon highLevelComponent, LinkedList<Polygon> lowLevelComponents, boolean bestCase) {
        this.highLevelComponent = highLevelComponent;
        this.lowLevelComponents = lowLevelComponents;
        contained = true;
        overLap = true;
        this.bestCase = bestCase;
    }

    /**
     * Performs a the 2D optimization service. The 2D optimization
     * will reposition the lower level components of a DecisionManager2D so they
     * maximize or minimize the area of the higher level area. If no optimized
     * area is found, shapes are returned to their original positions.
     */
    public void service() {
        LinkedList<Vector> best = new LinkedList<Vector>();
        //Adds all component locations into best.
        //If no optimized area is found, shapes are returned to their original locations.
        for (int i = 0; i < lowLevelComponents.size(); i++) {
            double tx = lowLevelComponents.get(i).getLocation().getX();
            double ty = lowLevelComponents.get(i).getLocation().getY();
            Vector t = new Vector(tx, ty);
            best.add(t);
        }

        //Place 1st low level component in the center
        Rectangle bx = highLevelComponent.getBoundingBox();
        lowLevelComponents.get(0).setLocation(bx.getLocation());

        optimize(1, bx.getWidth(), bx.getLength(), 0, best);

        //Sets each polygon to their optimized location.
        for (int i = 0; i < lowLevelComponents.size(); i++) {
            lowLevelComponents.get(i).setLocation(best.get(i));
        }
    }

    /**
     * Recursively performs the 2D optimization service.
     * @param polyNum The number of low-level componenets.
     * @param width The width of the high-level component's bounding box.
     * @param length The length of the high-level component's bounding box.
     * @param area The current optimal area calculated.
     * @param best Locations of low-level Components that have the optimal area.
     */
    private double optimize(int polyNum, double width, double length, double area, LinkedList<Vector> best) {
        if (polyNum == lowLevelComponents.size()) {
            //If no more polygons are left to place, return;
            return area;
        }

        Polygon poly = lowLevelComponents.get(polyNum);
        boolean goodArea = false;
        int numPlaced = 4;  //number of times a shapes position is moved around the 360 degrees around another shape
        //Trys 6 different positions for each polygon.
        for (int j = 1; j <= numPlaced; j++) {
            //radius of how far polygons are placed from each other.
            double radius = getRadius(lowLevelComponents.get(polyNum), lowLevelComponents.get(polyNum - 1));
            //Point to place next polygon.
            Point2D p = getRegularPolygonPoints(j, radius, lowLevelComponents.get(polyNum - 1), numPlaced);
            poly.setLocation(p.getLocation());

            area = optimize(polyNum + 1, width, length, area, best);

//            if(p.getX() < 10)
//                System.out.println("DFD");
            //Checks if the current set up of polygons meets all requirnments.
            goodArea = false;
            if (overLap) {
                if (contained && isContained()) {
                    goodArea = true;
                }
                if (!contained) {
                    goodArea = true;
                }
            }

            if (!overLap && !checkOverLap()) {
                if (contained && isContained()) {
                    goodArea = true;
                }
                if (!contained) {
                    goodArea = true;
                }
            }

            //If requirnments are met, find the area.
            if (goodArea) {
                double tempArea = findArea();
                if (bestCase && (tempArea > area)) {
                    best.clear();
                    //Get all locations for each polygon and store into an array.
                    for (int i = 0; i < lowLevelComponents.size(); i++) {
                        double tx = lowLevelComponents.get(i).getLocation().getX();
                        double ty = lowLevelComponents.get(i).getLocation().getY();
                        Vector t = new Vector(tx, ty);
                        best.add(t);
                    }
                    area = tempArea;
                } else if (!bestCase && (tempArea < area)) {
                    best.clear();
                    //Get all locations for each polygon and store into an array.
                    for (int i = 0; i < lowLevelComponents.size(); i++) {
                        double tx = lowLevelComponents.get(i).getLocation().getX();
                        double ty = lowLevelComponents.get(i).getLocation().getY();
                        Vector t = new Vector(tx, ty);
                        best.add(t);
                    }
                    area = tempArea;
                }
            }
        }

        return area;
    }

    /**
     * Sets whether the high-level Component can be interesected by low-level
     * Components and whether low-level Components can intersect one another.
     * @param contained <code>true</code> if low-level Components have to stay inside
     * the high-level Component; <code>false</code> otherwise.
     * @param overLap <code>true</code> if low-level Components can intersect one
     * another; <code>false</code> otherwise.
     */
    public void setIntersect(boolean contained, boolean overLap) {
        this.contained = contained;
        this.overLap = overLap;
    }

    /**
     * Determines whether the given Polygon is overlapping any other Polygons.
     * @param p Polygon to check for overlap.
     * @return <code>true</code> if the given Polygon overlaps another Polygon;
     * <code>false</code> otherwise.
     */
    private boolean checkOverLap() {

        for (int i = 0; i < lowLevelComponents.size(); i++) {
            for (int j = i + 1; j < lowLevelComponents.size(); j++) {
                try {
                    if (LinearAlgebra2D.intersect(lowLevelComponents.get(i), lowLevelComponents.get(j)) != null) {
                        return true;
                    }
                } catch (IllegalArgumentException e) {
                    //Don't overlap, continue checking
                }
            }
        }
        return false;
    }

    /**
     * Checks if the give Polygon is inside the high-level Component.
     * @param p the instance of Polygon to check.
     * @return <code>true</code> if it is contained; <code>false<code> otherwise.
     */
    private boolean isContained() {
        boolean isContained = true;
        for (int i = 0; i < lowLevelComponents.size(); i++) {
            isContained = LinearAlgebra2D.contains(highLevelComponent, lowLevelComponents.get(i));
            if (isContained == false) {
                return false;
            }
        }
        return isContained;
    }

    /**
     * Calculates the max distance the Polygons can be from each other so they
     * do not intersect.
     * @param a instance of Polygon used to compute the max distance.
     * @param b instance of Polygon used to compute the max distance.
     * @return the max distance the Polygons can be from each other so they
     * do not intersect.
     */
    private double getRadius(Polygon a, Polygon b) {
        double radius = 0;
        if (a.getBoundingBox().getLength() < a.getBoundingBox().getWidth()) {
            radius += a.getBoundingBox().getLength() / 2;
        } else {
            radius += a.getBoundingBox().getWidth() / 2;
        }

        if (b.getBoundingBox().getLength() < b.getBoundingBox().getWidth()) {
            radius += b.getBoundingBox().getLength() / 2;
        } else {
            radius += b.getBoundingBox().getWidth() / 2;
        }

        //Adds a cushion so they don't intersect every time
        return radius + 0.0001;
    }

    /**
     * Calculates the vertices of an n-gon and determines the vertice for the given Polygon.
     * @param point which Point in the n-gon to return.
     * @param radius the radius of the n-gon
     * @param polygon an instance of Polygon to be placed.
     * @return The point specified by the parameter.
     */
    private Point2D getRegularPolygonPoints(int point, double radius, Polygon polygon, int sides) {
        double x = 0;
        double y = 0;
        double angle = (2 * Math.PI) / sides;//number of sides

        for (int i = 0; i <= point; i++) {
            x = radius * Math.cos(angle + (i * angle)) * Math.cos(angle) - radius * Math.sin(angle + (i * angle)) * Math.sin(angle);
            y = radius * Math.sin(angle + (i * angle)) * Math.cos(angle) + radius * Math.cos(angle + (i * angle)) * Math.sin(angle);
        }

        return new Point2D(new Vector(x + polygon.getLocation().getX(), y + polygon.getLocation().getY()));
    }

    /**
     * Gets the total length of all LineSegments found while computing the area.
     * @param points a list of points found so far.
     * @return the total length of all LineSegments found while computing the area.
     */
    private double getSegmentLength(LinkedList<Point2D> points) {
//        LinkedList<Point2D> points = new LinkedList<Point2D>();
        LinkedList<LineSegment2D> newLines = new LinkedList<LineSegment2D>();
        double length = 0;

        if (points.size() == 0) {
            return 0;
        }

        //sort the points in the list according to their x coordinate
        sort(points);

        //for-loop that creates all the line segments with the points in points array list
        for (int i = 0; i < points.size() - 1; i++) {
            if ((points.get(i).getX() != points.get(i + 1).getX()) || (points.get(i).getY() != points.get(i + 1).getY())) {
                newLines.add(new LineSegment2D(points.get(i), points.get(i + 1)));
            }
        }

        //check to see if each line is fully contained in any poly, if so add to the length
        for (LineSegment2D line : newLines) {
            for (Polygon p : lowLevelComponents) {
                if (LinearAlgebra2D.contains(p, line)) {
                    length += line.getLength();
                    break;
                }
            }
        }

        return length;
    }

    /**
     * Gets the smallest y-coordinate of all the points that make up each low-level component.
     * @return the smallest y-coordinate of all the points that make up each low-level component
     */
    private double getSmallestY() {
        double yCoord = Double.MAX_VALUE;
        LinkedList<Point2D> points = new LinkedList<Point2D>();
        for (Polygon polygon : lowLevelComponents) {
            points.addAll(polygon.getListofPoints());
        }
        for (Point2D point : points) {
            if (point.getY() < yCoord) {
                yCoord = point.getY();
            }
        }
        return yCoord;
    }

    /**
     * Finds the covering area of the low-level components.
     * @return the covering area of the low-level components
     */
    private double findArea() {
        Rectangle bx = highLevelComponent.getBoundingBox();
        Point2D point1 = new Point2D(new Vector(0, 0));
        Point2D point2 = new Point2D(new Vector(bx.getLength(), 0));

        LineSegment2D baseLine = new LineSegment2D(point1, point2); //Line segment that will be moved up the high level area
        baseLine.setLocation(new Vector(bx.getLocation().getX(),
                bx.getLocation().getY() - (bx.getLength() / 2)));
        double area = 0;
        double accuracy = .25;      //height that the baseline will travel up each every iteration
        double baseLength = 0;      //length of the found length used to calculate the area
        double prevBaseLength = 0;  //length of the previous iterations baselength

        //moves the baseline to the bottom of the first polygon
        //don't know if there's a better method of doing this
        Vector location = baseLine.getLocation();
        baseLine.setLocation(new Vector(location.getX(), getSmallestY()));

        //do until the line no longer is in the high level component
        while (LinearAlgebra2D.intersect(baseLine, highLevelComponent) != null) {
            location = baseLine.getLocation();
            baseLine.setLocation(new Vector(location.getX(), location.getY() + accuracy));
            LinkedList<Point2D> lineSegments = new LinkedList<Point2D>();

            for (Polygon p : lowLevelComponents) {
                if (LinearAlgebra2D.intersect(baseLine, p) != null) {
                    Component2D line = LinearAlgebra2D.intersect(baseLine, p);
                    lineSegments.addAll(line.getListofPoints());
                }
            }

            //Adds points from baseLine incase a shape isn't contained in the high level area
            lineSegments.addAll(baseLine.getListofPoints());

            /* if else statement checks to see if the length has changed
             * if so it calculates area with the previous baselength
             * otherwise calculates area with baselength
             */
            baseLength = getSegmentLength(lineSegments);
            if (baseLength != prevBaseLength) {
                area += accuracy * prevBaseLength;
            } else {
                area += accuracy * baseLength;
            }
            prevBaseLength = baseLength;
        }

        return area;
    }

    /**
     * Sorts the list of points by their X value.
     * @param l List to be sorted.
     */
    private void sort(LinkedList<Point2D> l) {
        for (int i = 0; i < l.size(); i++) {
            for (int j = i; j < l.size(); j++) {
                if (l.get(j).getX() < l.get(i).getX()) {
                    Point2D p = l.get(j);
                    l.add(i, p);
                    l.remove(j + 1);
                }
            }
        }
    }
}